/*  

Cafechess Library: Cover basic chess programming needs, like GUI, Engine integration, 
FEN and PGN parsing.

                 \\|//
                 (o o)
--------------ooO-(_)-Ooo----------------------------------
Copyright (C) 2009  By Gregory A. Prentice Snoqualmie, WA
                    www.cafechess.org
                    cafechess@comcast.net
                      Oooo
--------------oooO----(  )---------------------------------
              (  )    (_/
               \_)

Microsoft Public License (Ms-PL)
               
Revisions:

Author        Date    Description:

*/
using System;
using System.Text;
using System.Collections;

namespace Cafechess.Chess.Validation
{
  using Bitboard = System.UInt64;

  /// <summary>
  /// This class represents the chess square number based on 0 through 63.
  /// Where 0 - 7 = a1 to g1 and 56 - 63 = a8 to h8.  It then translates
  /// the square number to the appropriate rotated bitboard square number.
  /// The idea here is to rid ourselves of the arrays needed to perform
  /// lookups, thus the amount of memory stored in the L2/L1 CPU cache.
  /// Which is based on internet discussions.
  /// Supported are L90, R90, L45, and R45.
  /// <code>
  ///                    Normal                     A8H1                     A1H8
  ///   56 57 58 59 60 61 62 63  56 49 42 35 28 21 14  7  56  1 10 19 28 37 46 55
  ///   48 49 50 51 52 53 54 55  48 41 34 27 20 13  6 63  48 57  2 11 20 29 38 47
  ///   40 41 42 43 44 45 46 47  40 33 26 19 12  5 62 55  40 49 58  3 12 21 30 39
  ///   32 33 34 35 36 37 38 39  32 25 18 11  4 61 54 47  32 41 50 59  4 13 22 31
  ///   24 25 26 27 28 29 30 31  24 17 10  3 60 53 46 39  24 33 42 51 60  5 14 23
  ///   16 17 18 19 20 21 22 23  16  9  2 59 52 45 38 31  16 25 34 43 52 61  6 15
  ///    8  9 10 11 12 13 14 15   8  1 58 51 44 37 30 23   8 17 26 35 44 53 62  7
  ///    0  1  2  3  4  5  6  7   0 57 50 43 36 29 22 15   0  9 18 27 36 45 54 63
  ///
  ///   a8 b8 c8 d8 e8 f8 g8 h8  a8 b7 c6 d5 e4 f3 g2 h1  a8 b1 c2 d3 e4 f5 g6 h7
  ///   a7 b7 c7 d7 e7 f7 g7 h7  a7 b6 c5 d4 e3 f2 g1 h8  a7 b8 c1 d2 e3 f4 g5 h6
  ///   a6 b6 c6 d6 e6 f6 g6 h6  a6 b5 c4 d3 e2 f1 g8 h7  a6 b7 c8 d1 e2 f3 g4 h5
  ///   a5 b5 c5 d5 e5 f5 g5 h5  a5 b4 c3 d2 e1 f8 g7 h6  a5 b6 c7 d8 e1 f2 g3 h4
  ///   a4 b4 c4 d4 e4 f4 g4 h4  a4 b3 c2 d1 e8 f7 g6 h5  a4 b5 c6 d7 e8 f1 g2 h3
  ///   a3 b3 c3 d3 e3 f3 g3 h3  a3 b2 c1 d8 e7 f6 g5 h4  a3 b4 c5 d6 e7 f8 g1 h2
  ///   a2 b2 c2 d2 e2 f2 g2 h2  a2 b1 c8 d7 e6 f5 g4 h3  a2 b3 c4 d5 e6 f7 g8 h1
  ///   a1 b1 c1 d1 e1 f1 g1 h1  a1 b8 c7 d6 e5 f4 g3 h2  a1 b2 c3 d4 e5 f6 g7 h8
  ///   
  /// It is VERY IMPORTANT to know that to help with reading of our bitboards we
  /// map each 8 bits of our ulong with the right most bit (actually bit 0) representing
  /// squares: 7, 15, 23, 31, 39, 47, 55, 63 and the left most bit representing
  /// squares: 0,  8, 16, 24, 32, 40, 48, 56 such that a hex number
  /// 
  /// chess columns    abcdefgh      unsigned long
  /// chess row 8 bits 76543210 = 0xFF00000000000000
  /// chess row 7 bits 76543210 = 0x00FF000000000000
  /// chess row 6 bits 76543210 = 0x0000FF0000000000
  /// chess row 5 bits 76543210 = 0x000000FF00000000
  /// chess row 4 bits 76543210 = 0x00000000FF000000
  /// chess row 3 bits 76543210 = 0x0000000000FF0000
  /// chess row 2 bits 76543210 = 0x000000000000FF00
  /// chess row 1 bits 76543210 = 0x00000000000000FF  
  /// </code>
  /// </summary>
  //[CLSCompliant(false)]
  public class BitboardSquare
  {

    public static Bitboard MaskHighBit = 0x8000000000000000;

    static string coLock="";
    /// <summary>
    /// Static array of our bitboard masks.
    /// </summary>
    static Bitboard[] coSquareMask;
    /// <summary>
    /// Mapping of algebraic square to numbers.
    /// </summary>
    static Hashtable coAlphaToSquare;
    static Hashtable coSquareToAlpha;
    static Hashtable coMaskToSquare;

    static BitboardSquare()
    {
      InitMasks();
    }
    /// <summary>
    /// Initialize our square to the first one.
    /// </summary>
    public BitboardSquare()
    {
      Square = 0;
    }

    /// <summary>
    /// Initialize our square to a specific location.
    /// </summary>
    /// <param name="square"></param>
    public BitboardSquare(int square)
    {
      Square = square;
    }
    /// <summary>
    /// Create the bitboard for single bit look up based on a square index.  
    /// </summary>
    static private void InitMasks()
    {

      lock(coLock)
      {
        if( coAlphaToSquare == null )
        {
          coSquareMask = new Bitboard[64];
          coAlphaToSquare = new Hashtable();
          coSquareToAlpha = new Hashtable();
          coMaskToSquare = new Hashtable();
          // Setup our mapping of square number to an associated bitboard
          //  where only the squares bit is set.
          int ndx=0,row,colm;
          Bitboard mask,maskndx;
          for(row=0; row<8; row++)
          {
            mask= ((Bitboard)0x0000000000000080) << (row*8);
            for(colm=0; colm<8; colm++)
            {
              maskndx = mask>>colm;
              coMaskToSquare[maskndx]=ndx;
              coSquareMask[ndx++]=maskndx;
            }
          }

          StringBuilder builder=new StringBuilder();
          char [] mapcol = { 'a','b','c','d','e','f','g','h' };
          char [] maprow = { '1','2','3','4','5','6','7','8' };  
          // Initialize our algebraic chess notation to square mapping.
          //  Example a8 = 56, a1 = 0, squares numbered 0-63
          ndx=0;
          for(row=0; row<8; row++)
          {
            for(colm=0; colm<8; colm++)
            {
              builder.Append(mapcol[colm]);
              builder.Append(maprow[row]);
              coSquareToAlpha[ndx] = builder.ToString();
              coAlphaToSquare[builder.ToString()]=ndx++;
              builder.Length=0;
            }
          }
        }
      }
    }

    /// <summary>
    /// Changes the numeric representation of a square into
    /// the algebraic notation.
    /// </summary>
    /// <param name="square"></param>
    /// <returns></returns>
    static public string SquareToAlpha(int square)
    {
      return (string)coSquareToAlpha[square];
    }
    /// <summary>
    /// Changes a algebraic square notation into an integer value
    /// of 0 through 63.
    /// </summary>
    /// <param name="square"></param>
    /// <returns></returns>
    static public int AlphaToSquare(string square)
    {
      return (int)coAlphaToSquare[square];
    }
    /// <summary>
    /// Expects a bitboard with only one bit set, returns the 
    /// integer value for that square 
    /// <param name="mask"></param>
    /// <returns></returns>
    static public int MaskToSquare(Bitboard mask)
    {
      return (int) coMaskToSquare[mask];
    }
    /// <summary>
    /// Expects a bitboard with only one bit set, returns the 
    /// algebraic string for the square 
    /// </summary>
    /// <param name="mask"></param>
    /// <returns></returns>
    static public string MaskToAlpha(Bitboard mask)
    {
      return SquareToAlpha(MaskToSquare(mask));
    }

    /// <summary>
    /// Return row number for an algebraic square notation.
    /// </summary>
    /// <param name="square"></param>
    /// <returns></returns>
    static public int Row(string square)
    {
      if(square.Length != 2)
        square = "00";
      return int.Parse(square[1].ToString());
    }
    /// <summary>
    /// Return the Column number for an algebraic square notation.
    /// </summary>
    /// <param name="square"></param>
    /// <returns></returns>
    static public int Column(string square)
    {
      int column = 0;
      switch(square[0])
      {
        case 'a':
          column = 1;
          break;
        case 'b':
          column = 2;
          break;
        case 'c':
          column = 3;
          break;
        case 'd':
          column = 4;
          break;
        case 'e':
          column = 5;
          break;
        case 'f':
          column = 6;
          break;
        case 'g':
          column = 7;
          break;
        case 'h':
          column = 8;
          break;
      }
      return column;
    }

    /// <summary>
    /// Will return the specified row or column's bitboard where only 
    /// this bits for that row/column are set.
    /// </summary>
    /// <param name="aChar"></param>
    /// <returns></returns>
    static public Bitboard RowOrColm(char aChar)
    {
      Bitboard mask = 0x00;
      switch(aChar)
      {

        case 'a':
          mask = 0x8080808080808080;
          break;
        case 'b':
          mask = 0x4040404040404040;
          break;
        case 'c':
          mask = 0x2020202020202020;
          break;
        case 'd':
          mask = 0x1010101010101010;
          break;
        case 'e':
          mask = 0x0808080808080808;
          break;
        case 'f':
          mask = 0x0404040404040404;
          break;
        case 'g':
          mask = 0x0202020202020202;
          break;
        case 'h':
          mask = 0x0101010101010101;
          break;
        case '1':
          mask = 0x00000000000000FF;
          break;
        case '2':
          mask = 0x000000000000FF00;
          break;
        case '3':
          mask = 0x0000000000FF0000;
          break;
        case '4':
          mask = 0x00000000FF000000;
          break;
        case '5':
          mask = 0x000000FF00000000;
          break;
        case '6':
          mask = 0x0000FF0000000000;
          break;
        case '7':
          mask = 0x00FF000000000000;
          break;
        case '8':
          mask = 0xFF00000000000000;
          break;
        default:
          throw new Exception("Invalid row/column charater");
      }
      return mask;  
    }
    /// <summary>
    /// Returns the bitboard mask with the single bit set which represents
    /// parameter algebraic notation.
    /// </summary>
    /// <param name="square"></param>
    /// <returns></returns>
    static public Bitboard Mask(string square){ return coSquareMask[(int)coAlphaToSquare[square]];}
    /// <summary>
    /// Returns the bitboard mask with the single bit set which represents
    /// the parameter integer square.
    /// </summary>
    /// <param name="square"></param>
    /// <returns></returns>
    static public Bitboard Mask(int square){ return coSquareMask[square]; }
    /// <summary>
    /// Gets the mask for the normal square.
    /// </summary>
    /// <returns></returns>
    public Bitboard SquareMask(){ return coSquareMask[coSquare]; }
    /// <summary>
    /// Gets the mask for our Rotated Left 45 bitboard
    /// </summary>
    /// <returns></returns>
    public Bitboard A8H1Mask(){ return coSquareMask[coA8H1Square]; }
    /// <summary>
    /// Gets the mask for our Rotated Right 45 bitboard
    /// </summary>
    /// <returns></returns>
    public Bitboard A1H8Mask(){ return coSquareMask[coA1H8Square]; }
    /// <summary>
    /// Gets the mask for our Rotated Right 90 bitboard
    /// </summary>
    /// <returns></returns>
    public Bitboard R90Mask(){ return coSquareMask[coR90Square]; }
    /// <summary>
    /// Gets the mask for our Rotated Left 90 bitboard
    /// </summary>
    /// <returns></returns>
    public Bitboard L90Mask(){ return coSquareMask[coL90Square]; }

    /// <summary>
    /// Represents a L45 bitboard square number.
    /// </summary>
    public int A8H1Square
    {get{ return coA8H1Square;}}
    private int coA8H1Square;
    /// <summary>
    /// Represents a R45 bitboard square number.
    /// </summary>
    public int A1H8Square
    {get{ return coA1H8Square;}}
    private int coA1H8Square;
    /// <summary>
    /// Represents a L90 bitboard square number.
    /// </summary>
    public int L90Square
    {get{ return coL90Square;}}
    private int coL90Square;
    /// <summary>
    /// Represents a R90 bitboard square number.
    /// </summary>
    public int R90Square
    {
      get{ return coR90Square;}
    }
    private int coR90Square;

    /// <summary>
    /// Set the square based on our algebraic notation.
    /// </summary>
    /// <param name="square"></param>
    public string AlphaSquare
    {
      set{ Square = (int)coAlphaToSquare[value]; }
      get{ return (string) coSquareToAlpha[Square]; }
    }
    /// <summary>
    /// The squares are number 0 through 63 and this is the only property 
    /// that allows you to set the square number.  The other four square
    /// properties: A8H1Square,A1H8Square,L90Square,R90Square are readonly 
    /// and are initialized when this property is set.    
    /// </summary>
    public int Square
    {
      set
      {
        coSquare = value;
        // **** The following formulas were provided by a friend: Xiaowei Sun
        // **** Explainations provided by: Gregory A. Prentice
        // 1) "(coSquare << 3)" multiply by 8.  You need to visualize what is happening here
        //  we extend our current counting pattern into eight boards: 8 x 64 = 512; where
        //  the count starts at 0 (bottom left) and ends at 511 (top right).  Now we are basically
        //  converting our square numbers to the multiples of 8 and these results all reside in the 
        //  first column (Column A in chess) ie: 0, 8, 16, 24, 32, 40, 48, 56, 64, 72...504
        // 2) "coSquare + step (1)".  Now add our original square value to our calculated value from
        //  the previous step.  This will move the position over to the correct diagonal that we are
        //  interested in.
        // 3) "step (2) & 63".  Now the interesting part, this could have been written: step (2) % 64.
        //  Which is basically limiting our output numbers to a modulo 64 counting system.  So as we shift
        //  our values higher into our extend boards our result will always be in the range: 0 thru 63.
        //  The reason for using the "& 63", instead of "%64", is the reduction in cpu instructions
        //  needed to execute the "&" vs the "%" math.        
        coA1H8Square = (coSquare + (coSquare << 3)) & 63;
        // 1) "(coSquare << 3)" multiply by 8.  Note to visualize what is happening here
        //  you need to extend our current counting pattern into eight boards: 8 x 64 = 512; where
        //  the count starts at 0 (bottom left) and ends at 511 (top right).  Now we are basically
        //  converting our square numbers to the multiples of 8 and these results all reside in the 
        //  first column (Column A in chess) ie: 0, 8, 16, 24, 32, 40, 48, 56, 64, 72...504
        // 2) "coSquare - step (1)", This is kind of cool if you think about it.  Since in step (1)
        //  we multiplied by 8, the result of this step will produce a negative number (unless 0).
        //  This is where things get interesting: negative numbers are stored in two's 
        //  compliment format: (-392 = 0xFFFF FE78 determined by ! 0xFFFF FE78 = 0x0000 0187 add 1 = 392).
        //  Pay attention to the bits for the next step. see: http://en.wikipedia.org/wiki/Twos_complement
        // 3) "step (2) & 63" 63 = (0x3F): A little bit of two complement magic!  Taking our value from the
        //  example above: 0xFFFF FE78 & 0x3F = 0x38 = 56 decimal.       
        coA8H1Square = (coSquare - (coSquare << 3)) & 63;               
        // 1) "(coSquare & 7)" always produces a value of 0 - 7
        //  for all squares.
        // 2) "<< 3" multiplying step (1) by 8.  Since we restricted the values in 
        //  step (1) to 0 thru 7, this opperation will always give us the 
        //  values in our left most column of numbers: 0, 8, 16, 24, 32, 40, 48, 56
        //  We now have our row value!
        // 3) "(coSquare >> 3)" Divides our original square by 8.  Since we are 
        //  dealing with integers, the fractional part is tossed there by giving
        //  us the values of 0 thru 7.  This gives us what column our number needs
        //  to be placed into.
        // 4) Now add results of step (2) and (3) together for our target square
        //	that holds the value stored in coSquare.
        coL90Square  = ((coSquare & 7) << 3) + (coSquare >> 3);
        // 1) "(coSquare & 7)" always produces a value of 0 - 7
        //  for all squares.
        // 2) "<< 3" multiplying step (1) by 8.  Since we restricted the values in 
        //  step (1) to 0 thru 7, this opperation will always give us the 
        //  values in our left most column of numbers: 0, 8, 16, 24, 32, 40, 48, 56
        //  We now have our row value!
        // 3) "(coSquare >> 3)" Divides our original square by 8.  Since we are 
        //  dealing with integers, the fractional part is tossed there by giving
        //  us the values of 0 thru 7.  This gives us what column our number needs
        //  to be placed into.
        // 4) "^ 7" Xor to step (3) which has the effect of providing the inverse operation
        //  where 7 ^ 7 = 0, 6 ^ 7 = 1, 5 ^ 7 = 2 ...
        // 5) Now add results of step (2) and (4) together for our target square
        //	that holds the value stored in coSquare.
        coR90Square  = ((coSquare & 7) << 3) + (coSquare >> 3) ^ 7;
      }
      get{ return coSquare; }
    }
    private int coSquare;
    /// <summary>
    /// Returns the algerbraic representation of our square.
    /// </summary>
    /// <returns></returns>
    override public string ToString(){ return BitboardSquare.SquareToAlpha(coSquare);}
  }
}
